﻿using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Configuration;
using System.Diagnostics;
using System.Text;
using System.Threading;
using OpenTK;

namespace LasRendering
{
    // Quadtree
    // http://en.wikipedia.org/wiki/Quadtree
    public class QuadTree
    {
        public QuadTree(Vector2 minPosition, Vector2 maxPosition, int numOfVertices)
        {
            int numOfVerticesPerQuadTreeLeafNode = Convert.ToInt32(ConfigurationManager.AppSettings["numOfVerticesPerQuadTreeLeafNode"]);
            int numOfNodes = numOfVertices / numOfVerticesPerQuadTreeLeafNode;
            int numOfLevels = (int)Math.Ceiling(Math.Log(numOfNodes, 4));
            numOfNodes = (int)Math.Pow(4, numOfLevels);
            var leafNodeList = new List<QuadTreeNode>(numOfNodes);
            this.Root = CreateQuadTreeNode(maxPosition.Y, minPosition.Y, maxPosition.X, minPosition.X, numOfLevels, leafNodeList);
            this.LeafNodes = leafNodeList.AsReadOnly();
            foreach (var leafNode in leafNodeList)
            {
                FindNodeNeighbors(leafNode);
            }
        }

        private static QuadTreeNode CreateQuadTreeNode(float northBound, float southBound, float eastBound, float westBound, int depth, List<QuadTreeNode> leafNodeList)
        {
            var node = new QuadTreeNode(northBound, southBound, eastBound, westBound);
            if (depth > 0)
            {
                var centerPosition = node.CenterPosition;
                node.NorthEastChild = CreateQuadTreeNode(northBound, centerPosition.Y, eastBound, centerPosition.X, depth - 1, leafNodeList);
                node.NorthWestChild = CreateQuadTreeNode(northBound, centerPosition.Y, centerPosition.X, westBound, depth - 1, leafNodeList);
                node.SouthEastChild = CreateQuadTreeNode(centerPosition.Y, southBound, eastBound, centerPosition.X, depth - 1, leafNodeList);
                node.SouthWestChild = CreateQuadTreeNode(centerPosition.Y, southBound, centerPosition.X, westBound, depth - 1, leafNodeList);
            }
            else
            {
                node.VertexIndexLink = new QuadTreeVertexIndexLink();
                node.NeighborVertexIndexLink = new QuadTreeVertexIndexLink();
                leafNodeList.Add(node);
            }
            return node;
        }

        private void FindNodeNeighbors(QuadTreeNode leafNode)
        {
            leafNode.NeighborNodes = new List<QuadTreeNode>(8);
            foreach (var node in this.LeafNodes)
            {
                if (leafNode.NorthBound == node.SouthBound ||
                    leafNode.SouthBound == node.NorthBound)
                {
                    if (leafNode.WestBound == node.EastBound ||
                        leafNode.WestBound == node.WestBound ||
                        leafNode.EastBound == node.WestBound)
                    {
                        leafNode.NeighborNodes.Add(node);
                        continue;
                    }
                }
                if (leafNode.WestBound == node.EastBound ||
                    leafNode.EastBound == node.WestBound)
                {
                    if (leafNode.NorthBound == node.SouthBound ||
                        leafNode.NorthBound == node.NorthBound ||
                        leafNode.SouthBound == node.NorthBound)
                    {
                        leafNode.NeighborNodes.Add(node);
                        continue;
                    }
                }
            }
        }

        public QuadTreeNode Root
        {
            private set;
            get;
        }

        public ReadOnlyCollection<QuadTreeNode> LeafNodes
        {
            private set;
            get;
        }

        public Vector3 MinPosition
        {
            internal set;
            get;
        }

        public Vector3 MaxPosition
        {
            internal set;
            get;
        }

        private float vertexAvgSize;
        public float VertexAvgSize
        {
            internal set
            {
                this.vertexAvgSize = value;
                float neighborsRangeFactor = Convert.ToSingle(ConfigurationManager.AppSettings["neighborsRangeFactor"]);
                neighborRange = vertexAvgSize * neighborsRangeFactor * 2;
            }
            get
            {
                return this.vertexAvgSize;
            }
        }

        public int Count
        {
            internal set;
            get;
        }

        private QuadTreeNode lastNodeForAdding;

        public void AddVertexIndex(Vector2 position, int index)
        {
            if (this.lastNodeForAdding != null && IsInBound(this.lastNodeForAdding, position))
            {
                AddVertexIndex(this.lastNodeForAdding, position, index);
            }
            else
            {
                if (!IsInBound(this.Root, position))
                {
                    Debug.Fail(null);
                }

                this.lastNodeForAdding = AddVertexIndex(this.Root, position, index);
            }

            AddVertexIndexForNeighborhood(this.lastNodeForAdding, position, index);
        }

        public void OffsetBoundary(Vector2 offset)
        {
            OffsetBoundary(this.Root, offset);
        }

        public delegate bool IsPositionVisibleFunc(Vector2 position, out Vector2 uv);

        public void EnumerateVisibleNode(
            Func<Vector2, Vector2> projectToScreenZeroToOneFunc,
            Action<QuadTreeNode, Vector2, Vector2, Vector2, Vector2> visibleFunc,
            Action<QuadTreeNode> invisibleFunc)
        {
            EnumerateVisibleNode(this.Root, false, false, projectToScreenZeroToOneFunc, visibleFunc, invisibleFunc);
        }

        private static void EnumerateVisibleNode(
            QuadTreeNode node,
            bool predicatedVisible,
            bool predicatedInvisible,
            Func<Vector2, Vector2> projectToScreenZeroToOneFunc,
            Action<QuadTreeNode, Vector2, Vector2, Vector2, Vector2> visibleFunc,
            Action<QuadTreeNode> invisibleFunc)
        {
            if (predicatedVisible)
            {
                if (IsLeafNode(node))
                {
                    Vector2 uv0 = projectToScreenZeroToOneFunc(new Vector2(node.WestBound, node.NorthBound));
                    Vector2 uv1 = projectToScreenZeroToOneFunc(new Vector2(node.WestBound, node.SouthBound));
                    Vector2 uv2 = projectToScreenZeroToOneFunc(new Vector2(node.EastBound, node.NorthBound));
                    Vector2 uv3 = projectToScreenZeroToOneFunc(new Vector2(node.EastBound, node.SouthBound));
                    visibleFunc(node, uv0, uv1, uv2, uv3);
                }
                else
                {
                    EnumerateVisibleNode(node.NorthEastChild, true, false, projectToScreenZeroToOneFunc, visibleFunc, null);
                    EnumerateVisibleNode(node.NorthWestChild, true, false, projectToScreenZeroToOneFunc, visibleFunc, null);
                    EnumerateVisibleNode(node.SouthEastChild, true, false, projectToScreenZeroToOneFunc, visibleFunc, null);
                    EnumerateVisibleNode(node.SouthWestChild, true, false, projectToScreenZeroToOneFunc, visibleFunc, null);
                }
            }
            else if (predicatedInvisible)
            {
                if (IsLeafNode(node))
                {
                    invisibleFunc(node);
                }
                else
                {
                    EnumerateVisibleNode(node.NorthEastChild, false, true, null, null, invisibleFunc);
                    EnumerateVisibleNode(node.NorthWestChild, false, true, null, null, invisibleFunc);
                    EnumerateVisibleNode(node.SouthEastChild, false, true, null, null, invisibleFunc);
                    EnumerateVisibleNode(node.SouthWestChild, false, true, null, null, invisibleFunc);
                }
            }
            else
            {
                Vector2 uv0 = projectToScreenZeroToOneFunc(new Vector2(node.WestBound, node.NorthBound));
                Vector2 uv1 = projectToScreenZeroToOneFunc(new Vector2(node.WestBound, node.SouthBound));
                Vector2 uv2 = projectToScreenZeroToOneFunc(new Vector2(node.EastBound, node.NorthBound));
                Vector2 uv3 = projectToScreenZeroToOneFunc(new Vector2(node.EastBound, node.SouthBound));



                if (uv0.X > 0 && uv0.X < 1 && uv0.Y > 0 && uv0.Y < 1 &&
                    uv1.X > 0 && uv1.X < 1 && uv1.Y > 0 && uv1.Y < 1 &&
                    uv2.X > 0 && uv2.X < 1 && uv2.Y > 0 && uv2.Y < 1 &&
                    uv3.X > 0 && uv3.X < 1 && uv3.Y > 0 && uv3.Y < 1)
                {
                    if (IsLeafNode(node))
                    {
                        visibleFunc(node, uv0, uv1, uv2, uv3);
                    }
                    else
                    {
                        EnumerateVisibleNode(node.NorthEastChild, true, false, projectToScreenZeroToOneFunc, visibleFunc, null);
                        EnumerateVisibleNode(node.NorthWestChild, true, false, projectToScreenZeroToOneFunc, visibleFunc, null);
                        EnumerateVisibleNode(node.SouthEastChild, true, false, projectToScreenZeroToOneFunc, visibleFunc, null);
                        EnumerateVisibleNode(node.SouthWestChild, true, false, projectToScreenZeroToOneFunc, visibleFunc, null);
                    }
                }
                else if (
                    (uv0.X < 0 && uv1.X < 0 && uv2.X < 0 && uv3.X < 0) ||
                    (uv0.X > 1 && uv1.X > 1 && uv2.X > 1 && uv3.X > 1) ||
                    (uv0.Y < 0 && uv1.Y < 0 && uv2.Y < 0 && uv3.Y < 0) ||
                    (uv0.Y > 1 && uv1.Y > 1 && uv2.Y > 1 && uv3.Y > 1))
                {
                    if (invisibleFunc != null)
                    {
                        if (IsLeafNode(node))
                        {
                            invisibleFunc(node);
                        }
                        else
                        {
                            EnumerateVisibleNode(node.NorthEastChild, false, true, null, null, invisibleFunc);
                            EnumerateVisibleNode(node.NorthWestChild, false, true, null, null, invisibleFunc);
                            EnumerateVisibleNode(node.SouthEastChild, false, true, null, null, invisibleFunc);
                            EnumerateVisibleNode(node.SouthWestChild, false, true, null, null, invisibleFunc);
                        }
                    }
                }
                else
                {
                    if (IsLeafNode(node))
                    {
                        visibleFunc(node, uv0, uv1, uv2, uv3);
                    }
                    else
                    {
                        EnumerateVisibleNode(node.NorthEastChild, false, false, projectToScreenZeroToOneFunc, visibleFunc, invisibleFunc);
                        EnumerateVisibleNode(node.NorthWestChild, false, false, projectToScreenZeroToOneFunc, visibleFunc, invisibleFunc);
                        EnumerateVisibleNode(node.SouthEastChild, false, false, projectToScreenZeroToOneFunc, visibleFunc, invisibleFunc);
                        EnumerateVisibleNode(node.SouthWestChild, false, false, projectToScreenZeroToOneFunc, visibleFunc, invisibleFunc);
                    }
                }
            }
        }

        private static void OffsetBoundary(QuadTreeNode node, Vector2 offset)
        {
            node.EastBound -= offset.X;
            node.WestBound -= offset.X;
            node.NorthBound -= offset.Y;
            node.SouthBound -= offset.Y;
            node.CenterPosition -= offset;
            if (!IsLeafNode(node))
            {
                OffsetBoundary(node.NorthEastChild, offset);
                OffsetBoundary(node.SouthEastChild, offset);
                OffsetBoundary(node.NorthWestChild, offset);
                OffsetBoundary(node.SouthWestChild, offset);
            }
        }

        private static QuadTreeNode AddVertexIndex(QuadTreeNode node, Vector2 position, int index)
        {
            if (IsLeafNode(node))
            {
                node.VertexIndexLink.Add(index);
                return node;
            }

            if (position.X < node.CenterPosition.X)
            {
                if (position.Y > node.CenterPosition.Y)
                {
                    return AddVertexIndex(node.NorthWestChild, position, index);
                }
                else
                {
                    return AddVertexIndex(node.SouthWestChild, position, index);
                }
            }
            else
            {
                if (position.Y > node.CenterPosition.Y)
                {
                    return AddVertexIndex(node.NorthEastChild, position, index);
                }
                else
                {
                    return AddVertexIndex(node.SouthEastChild, position, index);
                }
            }
        }

        private static void AddVertexIndexForNeighborhood(QuadTreeNode node, Vector2 position, int index)
        {
            foreach (var neighbor in node.NeighborNodes)
            {
                if (IsNeighbor(neighbor, position))
                {
                    neighbor.NeighborVertexIndexLink.Add(index);
                }
            }
        }

        private static bool IsInBound(QuadTreeNode node, Vector2 position)
        {
            if (position.X < node.WestBound || position.X > node.EastBound ||
                position.Y < node.SouthBound || position.Y > node.NorthBound)
            {
                return false;
            }

            return true;
        }

        private static float neighborRange;
        private static bool IsNeighbor(QuadTreeNode node, Vector2 position)
        {
            float n = node.NorthBound - neighborRange;
            float w = node.WestBound - neighborRange;
            float s = node.SouthBound + neighborRange;
            float e = node.EastBound + neighborRange;

            if (position.X < w || position.X > e ||
                position.Y < s || position.Y > n)
            {
                return false;
            }

            if (IsInBound(node, position))
            {
                return false;
            }

            return true;
        }

        private static bool IsLeafNode(QuadTreeNode node)
        {
            return node.NorthEastChild == null;
        }
    }
}
